\documentclass[a4paper,10pt]{article}

\usepackage{graphics}
%\usepackage{listings}
\usepackage[french]{babel}
\usepackage[utf8x]{inputenc}
\usepackage{graphicx}
\usepackage{vmargin}
\setpapersize{A4}
\setmarginsrb  %default values
{25mm}  % leftmargin : 30mm
{20mm}  % topmargin
{25mm}  % rightmargin
{20mm}  % bottommargin : 25mm
{12pt}  % headheight
{5mm}   % headsep
{12pt}  % footheight
{10mm}  % footskip


\title{Recherche Opérationnelle}

\author{Salim \textsc{Bensiali}\\Fabien \textsc{Bourrel}}

\begin{document}
\maketitle
\begin{abstract}
Rapport du projet de Recherche Opérationnelle 2009-2010. 
Conception d'un solveur et générateur de sudoku.
Recherche de trajectoire optimale modélisée par une proie.
\end{abstract}

\tableofcontents
\newpage

\section{Proie}

\subsection{Présentation du problème}
On considère la trajectoire rectiligne d'une 'proie' sur une demi-droite.\\
On connait les vitesses, accélérations et positions à l'instant initial de 
la proie donc on peut calculer sa trajectoire.\\
La trajectoire de la proie est restreinte en focntion de contrainte 
l'interdisant de passat dans certaines zones du plan.

\subsection{Résolution par algorithme génétique}

Un algorithme génétique est une procédure stochastque d'optimisation globale 
qui cherche à optimiser un critère en faisant évoluer une population de solutions 
candidates selon des règles proches de celles qui régissent l'évolution naturelle... \\
Plus les individus d'une population sont performants, plus ils ont de chance de 
survivre, de se reproduire, de donner donc la vie à des descendants aux potentialités 
toujours meilleures issues des opérationes essentielles de la reproduction : 
recombinaisons et mutations... \\

Ainsi, nous avons codés les 2 fonctions : croisement et mutation en TP qui 
peuvent se résumer comme suit :
\begin{verbatim}
 ### CROISEMENT ###
SI un nb aleatoire choisi uniformément entre 0 et 1 est inférieur à la proba de croisement
ALORS
  Tirer au hasard un 'site' de coupure pour le croisement : position entière entre 2 et lchrom = n
  Construire par échange des sous-chromosomes des géniteurs les 2 descendants
SINON	pas de changement : les enfants sont les parents
FINSI
\end{verbatim}

\begin{verbatim}
 ### MUTATION ###
POUR toutes les composantes du vecteur à muter FAIRE
  SI un nb aléatoire choisi uniformément entre 0 et 1 est inférieur à la proba de mutation
  ALORS
    Tirer au hasard une permutation aléatoire dans l'intervalle [-amplitude, +amplitude]
    Mettre à jour la composante du vecteur muté
  FINSI
FINPOUR
\end{verbatim}

\subsection{Résolution par mipSolveur}

Dans cette partie, nous avons utilisé un algorithme de résolution de problème linéaire 
mixte (MILP : Mixed Integer Linear Program) qui est un problème où toutes les équations 
sont linéaires et dont les variabes sont soit réelles, soit entières.\\
Il ne reste plus qu'à résoudre le problème donné dans le sujet.\\
Pour celà nous avons utilisé Matlab et créé ce fichier qui permet de calculer la matrice 
solution ainsi que la matric b et c de l'équation :
\begin{verbatim}
 % calcul de c
for i = n+1 : 2*n
    c(i) = 1;
end

% Calcul de A
for i = 1:n
    A(i,i)=1;
    A(i,i+n)=-1;
end
for i = (n+1) : (2*n)
    A(i, i-n) = -1;
    A(i, i-n+n) = -1;
end
for i = (2*n+1): 3*n
    for j = 1 :(i-2*n)
        A(i,j) = -(i-2*n)+j-1;
    end
end

for i = 3*n+1:3*n+M
        A(i, i-n) = -MM;
end
for i = 3*n+M+1:3*n+2*M
        A(i, i-n-M) = MM;
end

for i = 3*n+1:3*n+M
    timp = timpact(i-3*n);
    for j = 1:n
        if timp ~= 0
            A(i,j) = timp;
            timp = timp - 1;
        else
            A(i,j) = 0;
        end
    end
end

for i = 3*n+1+M:3*n+M+M
    timp = timpact(i-3*n-M);
    for j = 1:n
        if timp ~= 0
            A(i,j) = -timp;
            timp = timp - 1;
        else
            A(i,j) = 0;
        end
    end
end

% Calcul de b
for i=1:(2*n)
    b(i) = 0;
end
for i=(2*n+1):3*n
    b(i) = (i-2*n)*v0;
end
for i = (3*n+1): 3*n+M
    b(i) = pimmin(i - 3*n)- b(i-M);
end
for i = (3*n+M+1) : 3*n + 2*M
    b(i) = MM - pimmax(i -3*n-M)+b(i-2*M);
end
\end{verbatim}

\section{Sudoku}

\subsection{Introduction}

La grille de jeu du sudoku est un carré de neuf cases de côté, subdivisé en autant 
de sous-grilles carrées identiques, appelées « régions ».
La règle du jeu générique : chaque ligne, colonne et région ne doit contenir qu’une 
seule fois tous les chiffres de un à neuf.

Le but de ce projet est de manipuler des structures qui permettront de résoudre, 
générer et créer des sudokus possédant une et une seule solution. \\
Le choix du langage ne nous a malheureusement pas été laissé, nous avons dû effectuer 
les algorithmes en Matlab.
\begin{figure}[!h]
 \centering
 \includegraphics[width = 4.5 cm, height = 3 cm]{Matlab.png}
\end{figure}

Pour réaliser des grilles de sudokus possédant le moins de valeurs initiales possibles, 
il nous faut donc savoir :
\begin{itemize}
 \item Résoudre des sudokus.
 \item Générer aléatoirement des grilles de sudokus pleines et valides.
 \item Utiliser un algorithme permettant d'enlever des cases à un sudoku tout en gardant 
une solution unique à ce sudoku.
\end{itemize}


\subsection{Résolution d'un sudoku}

Pour la résolution d'un sudoku, il y a plusieurs techniques permettant de parvenir au résultat.
Tout d'abord, on peut utiliser une technique qui permet de résoudre la plupart des sudokus faciles : 
on teste sur chaque ligne, chaque colonne, chaque carré de 3x3 et chaque case s'il n'y a pas 
une valeur unique que l'on pourrait mettre.\\
Tant qu'on effectue des modifications, on recommence au début (fichier \verb resol_facile.m ).
Pour des grilles ayant un niveau de difficulté plus élevé, il faut donc changer d'algorithm 
(fichier \verb Sudoku_ameliore.m ).\\
Pour celà, nous avons pris un algorithme qui, lorsqu'il se retrouve dans une situation de blocage 
avec la première technique. C'est-à-dire qu'il y a au moins 2 possibilités minimum sur chaque case 
ou que le sudoku est totalement rempli, on cherche l'endroit où il y a le moins de possibilité et 
on crée autant de sudoku que de possibilité en remplaçant la valeur de la case par une valeur 
possible correspondante.\\
Ainsi, on a tous les cas possibles pour le sudoku.\\

On stocke ces matrices et on recommence l'algorithme sur une de celles-ci jusqu'à trouver la 
solution (car elle est unque) ou retrouver un blocage et recréer d'autres matrices que l'on 
stockera également dans une liste.\\
Tant que la liste n'est pas vide on continue.\\

Voici ce que celà peut donner en Matlab :
\begin{verbatim}
 while size(L) ~= 0
    nb_possibilite = 10;
    taille = size(L, 2);
    essai = L{1, 1};
    if (taille == 1)
        L= {};
    else
        L = L(2:taille);
    end
    [sol, cube, marche, fini] = resol_facile(essai);
% Des qu'on trouve une solution on s'arrete. A utiliser seulement pour la résolution d'un sudoku.
    if (fini == 1)
        return;
    end
% On est dans le cas où le sudoku marche mais il n'est pas fini, donc il faut faire des suppositions.
    if (marche == 1)
      for i= 1:9
        for j=1:9
          if (sol(i, j) == 0)
            somme = 0;
% On calcule le nombre de possibilité sur la case vide
            somme = sum(cube(i, j, :));
% Si c'est plus petit alors on récupère les positions.
            if (somme < nb_possibilite)
	      i_final = i;
	      j_final = j;
	      nb_possibilite = somme;
            end
	  end
        end
      end
% On calcule les différentes possibilités et on les rajoute à la liste.
      for k=1:9
        if (cube(i_final, j_final, k) == 1)
	  S = sol;
	  S(i_final, j_final) = k;
	  L = [ S L ];
        end
      end
    end
% Dans le cas où marche = 0, on reviens au début car on a déjà enlevé le sudoku de la liste L.
end
\end{verbatim}


\subsection{Génération d'une grille pleine}

Afin de générer une grille pleine respectant les règles de base du Sudoku, à savoir neuf chiffres
différents dans chaque ligne, colonne et bloc, on procède de la manière suivante :\\
\begin{itemize}
 \item On remplit toutes les lignes avec les 9 chiffres de façon aléatoire.\\
 \item Une fois la grille remplie, il est nécessaire de la modifier pour faire en sorte que les 
colonnes et lesblocs vérifient également les conditions. Pour cela, on choisit aléatoirement une 
ligne de la grille, puisdeux colonnes. On dispose ainsi de deux cases d’une même ligne. On effectue 
alors une permutationdes deux valeurs, puis on procède au calcul d’un certain critère que l’on veut 
annuler. Si ce critèrediminue, la permutation est acceptée. Dans le cas contraire, la permutation 
est annulée, et les deux valeurs sont de nouveau échangées. Cette manipulation est effectuée 
jusqu’à obtenir un critère nul.\\
 \item le critère choisi est l’erreur (l’écart) entre notre grille et une grille correcte, 
vérifiant les conditions.
Il s’annule lorsque notre grille devient valide. Voici la manière dont il est calculé : Pour chaque
colonne et chaque bloc, un vecteur de taille 9 est construit. On y range le nombre d’occurences de
chaque chiffre : par exemple, si le 1 est présent trois fois dans la colonne ou le bloc, la première 
composante du
vecteur sera un 3, etc. Si l’on considère un tel vecteur pour une grille valide, toutes ses
composantes valent 1. En effet, chaque chiffre se trouve une et une seule fois dans chaque colonne
et dans chaque bloc. Ainsi, en testant chaque colonne et chaque bloc et en calculant la 'distance' à 
laquelle on se situe d'un sudoku valide, on peut voir si on se rapproche ou non d'une solution 
grâce à la permutation.
\end{itemize}


Par exemple, on pourrait avoir une matrice comme celà au début : \\
\begin{verbatim}
     2     3     4  |   9     5     1  |   7     6     8
     7     4     3  |   5     6     2  |   8     9     1
     8     7     4  |   1     3     9  |   2     6     5
     ---------------|------------------|----------------
     4     2     5  |   7     8     1  |   3     9     6
     8     5     4  |   6     7     3  |   2     1     9
     5     8     7  |   3     2     4  |   6     1     9
     ---------------|------------------|----------------
     5     2     4  |   1     6     9  |   8     7     3
     2     7     4  |   1     6     5  |   8     3     9
     2     4     7  |   3     6     1  |   8     5     9
\end{verbatim}
\begin{tabbing}
\= \\ 
\end{tabbing}
qui va devenir ceci après plusieurs permutations : \\
\begin{verbatim}
     7     3     4  |   9     1     5  |   8     6     2
     6     8     5  |   7     4     2  |   9     3     1
     1     9     2  |   6     3     8  |   7     4     5
     ---------------|------------------|----------------
     4     2     3  |   1     7     6  |   5     9     8
     8     7     6  |   5     9     3  |   2     1     4
     5     1     9  |   2     8     4  |   6     7     3
     ---------------|------------------|----------------
     3     6     1  |   8     5     9  |   4     2     7
     9     4     8  |   3     2     7  |   1     5     6
     2     5     7  |   4     6     1  |   3     8     9
\end{verbatim}
\begin{tabbing}
\= \\ 
\end{tabbing}

\subsection{Algorithme basique d'élimination de cases}

Cet algorithme est assez intuitif, il permet, à partir d'une grille pleine, de générer un 
sudoku possédant une seule solution et ayant le moins de cases non vides à l'instant initial.
Ainsi, à partir du sudoku plein, on enlève une case au hasard et on teste s'il reste une 
seule solution ou pas.\\
S'il n'y en a qu'une on garde cette modification puis on prend une autre case, s'il y en a 
plusieurs on remet la case et on reprend une autre case au hasard.\\

Ce qui donne :
\begin{verbatim}
 while (p<nb_iter)
    i = round(rand*8 + 1);
    j = round(rand*8 + 1);
    while (sudo(i, j) == 0)
        i = round(rand*8 + 1);
        j = round(rand*8 + 1);
    end
    k = sudo(i, j);
    sudo(i, j) = 0;
    nb_sol = sudoku_contrainte_all(sudo);
    if (nb_sol ~= 1)
        sudo(i, j) = k;
    else
% energie_finale est le nombre qui définit le nombre de cases non vides dans le sudoku
        energie_finale = energie_finale - 1;
        sudo_final = sudo;
    end
    p = p + 1;
end
\end{verbatim}

Avec cet algorithme, on trouve la plupart du temps des sudokus possédant environ 
25 composantes non vides, ce qui pourrait être considéré comme des sudokus moyens/difficiles.

\subsection{Algorithme du recuit simulé}

    Dans un problème d’optimisation, on cherche à déterminer le minimum d’un certain critère. Que se
passe-t-il si le problème n’est pas convexe, c’est-à-dire s’il peut admettre des minima locaux ? L’arrêt
de la recherche s’effectuant lorsqu’on obtient un minimum (local), il serait alors impossible d’obtenir un
maximum global si le chemin menant de l’un à l’autre doit faire augmenter le critère.\\

Pour palier à ce problème, considérons l’algorithme du recuit simulé : tant que le critère varie et tant que
le nombre d’itérations ne dépasse pas le seuil :
\begin{itemize}
 \item si le critère diminue, tout va bien et on poursuit la recherche.
 \item si le critère augmente - cas qui nous intéresse potentiellement pour passer d’un minimum local à 
un minimum global - on l’accepte avec une certaine probabilité, dépendant de la variation du critère 
($\delta$) et d’une grandeur du problème appelée température (T).\\
\end{itemize}
\begin{math} T_{j} = T_{0} ∗ a^{j} \end{math}, où \begin{math}T_{0}\end{math} température finale, j le 
nombre d’itérations et a un coefficient d’amortissement
(loi de décroissance de la température).\\
Alors la probabilité d’acceptation à la \begin{math}j^{eme}\end{math} itération est 
exp(\begin{math}−\end{math}$\delta$/\begin{math}T_{j}\end{math}).\\

On génère alors un nombre aléatoire. S’il est inférieur à la probabilité d’acceptation, on accepte le nouveau
critère, sinon on continue. En faisant varier le nombre d’itérations, la température initiale et
 l’amortissement, il est possible de contrôler la vitesse d’exécution, la qualité des grilles, mais 
pas leur difficulté.\\
En effet, cette dernière n’est déterminée que par la nature des méthodes utilisées pour la résolution de la
grille. Il est cependant tout à fait possible de déterminer quelles méthodes de résolution ont été utilisées
et d’en déduire la difficulté de la grille.\\
    Grâce aux tests effectués en faisant varier les différents paramètres, nous obtenons des grilles de
sudokus dont le nombre de cases non vides est compris entre 20 et 25.
\newpage
Voici un exemple de grille que l'on obtient :
\begin{figure}[!h]
 \centering
 \includegraphics[width=10cm, height=10cm]{Capture.png}
\end{figure}

\section{Conclusion}

L'idée de travailler sur un sudoku pour un projet est bien d'autant plus que la plupart des étudiants 
se sont souvent retrouvés un jour ou l'autre devant un sudoku.\\
Même si les algorithmes ne sont pas réellement compliqués, celà nous oblige à bien gérer les 
différentes structures que l'on implémente.\\
Par contre, l'usage de Matlab est un peu excessif sur ce genre de projet car ce n'est pas réellement 
prévu pour effectuer des recherches dans des structures. Ce qui augmente considérablement le temps 
d'exécution comparés à un programme fait en Java ou même en C.

\end{document}